The invention relates to estimating the usefulness of an item in a collection of information.
One context in which selection of items from a collection of information (e.g., a database) is useful is a xe2x80x9csearch engine.xe2x80x9d A typical search engine takes an alphanumeric query from a user (a xe2x80x9csearch stringxe2x80x9d) and returns to the user a list of one or more items from the database that satisfy some or all of the criteria specified in the query.
Although search engines have been in use for many years, for example in connection with the Westlaw(copyright) or Lexis(copyright) and legal databases, their use has risen dramatically with the development of the World Wide Web. Because the World Wide Web comprises a very large number of discrete items, which come from heterogeneous sources, and which are not necessarily known in advance to the user, search engines that can identify relevant Web-based information resources in response to a user query have become important tools for doing Web-based research.
With tens or hundreds of millions of individual items potentially accessible over the Web, it is not unusual for a single query to a search engine to result in the return of hundreds or thousands of items of varying quality from which the user must manually select those that may be truly useful. This manual evaluation can be a time consuming and frustrating process.
One approach to managing the large number of potentially relevant items returned by a search engine is for the engine to rank the items for relevance before displaying them. Specifically, the items may be ranked according to some relevance metric reflecting how well the intrinsic features of a particular item (e.g., its textual content, its location, the language in which it is written, the date of its creation, etc.) match the search criteria for the particular search. A number of relevance metrics are described, e.g., in Manning and Schuitze, xe2x80x9cFoundations of Statistical Natural Language Processingxe2x80x9d, MIT Press, Cambridge, Mass. (1999) pp. 529-574 and U.S. Pat. No. 6,012,053.
Ranking items based on a measure of relevance to a search query is, however, often an imperfect measure of the actual relative usefulness of those items to users. In particular, a relevance metric may not take into account certain factors that go into a user""s ultimate evaluation of the usefulness of a particular item: e.g., how well the item is written or designed, the reliability or authority of the source of the information in the item, or the user""s prior familiarity with the item. Thus, a search engine presented with a query for xe2x80x9cHistory of the United Statesxe2x80x9d might consider an encyclopedia article by a well-known historian and a term paper written by a high school student to be of equal relevance, even though the former is far more likely to be useful to most users than the latter.
Ranking items by relevance is also susceptible to xe2x80x9cspoofing.xe2x80x9d xe2x80x9cSpoofingxe2x80x9d refers to attempting to artificially improve the apparent relevance of a particular item with respect to particular search criteria by altering the item in a misleading way. For example, it is common for search engines to evaluate the relevance of a Web page based on the contents of meta-tags. Meta-tags are lists of keywords that are included in the HTML source of a Web page but which are not normally displayed to users by Web browsers. Web site operators who wish to increase the number of visits to their Web sites commonly attempt to spoof search engines by creating meta-tags that contain either keywords that are not truly indicative of the displayed contents of the page (but which are likely to match a large number of queries), or by creating meta-tags that include multiple instances of arguably appropriate keywords (thus inflating the relative importance of that keyword to the Web page).
Some search techniques have attempted to incorporate information about subjective user preferences within a relevance metric. One such method entails modifying the relevance score of an individual item (with respect to a search term or phrase) according to how often the item is selected when displayed in response to a query containing the search term or phrase. However, this technique may provide unsatisfactory results under conditions of sparse data (i.e., where the individual items were selected by users in response to queries containing the search term or phrase a relatively small number of times).
The present invention provides a system and method for estimating the usefulness of an item in a collection of information.
In general, in one aspect, a first measure of the usefulness of the item with respect to the first set of criteria is determined. A measure of the quality of the item is determined. A second measure of the usefulness of the item is determined based on the first measure of usefulness and the measure of quality.
Embodiments of the invention may have one or more of the following features.
A measure of the relevance of the item to the first set of criteria is determined. A selection rate of the item is predicted based on the measure of relevance.
Opportunities for user selection of the item are provided. The actual overall popularity of the item is determined. The overall popularity of the item is predicted. The measure of quality of the item is determined based on the actual popularity of the item and the predicted overall popularity of the item.
A plurality of sets of items containing the item is displayed. A choice of the item from at least one of the sets of displayed items is received from a user.
At least one set of items containing the item is displayed ranked in accordance to a relevance metric.
At least one set of items containing the item is displayed ranked in accordance to a measure of the usefulness of the respective items.
Users are provided with opportunities to present sets of criteria. Respective measures of the relevance of the item to respective sets of criteria presented by users are determined. Respective selection rates of the item are predicted based on the respective measures of relevance. The overall popularity of the item is predicted based on the respective predicted selection rates.
Respective measures of the popularity of the respective sets of criteria among users are determined. The overall popularity of the item is predicted based on the respective predicted selection rates and the respective measures of the popularity of the respective sets of criteria.
The rank of the item in a list of items relevant to the set of criteria and ranked according to a relevance metric is determined.
The number of times that the item was selected by a user during a pre-determined period of time is determined.
The collection of information comprises a catalog of information resources available on a public network.
The collection of information comprises a catalog of information available on the World Wide Web.
Data concerning selection of the item by users is collected. An anti-spoof criterion is applied to the data. The actual overall popularity of the item is decreased based on the results of applying the anti-spoof criterion to the data.
Respective first measures of the usefulness of respective other items in the collection of information with respect to the first set of criteria are determined. Respective measures of the quality of the respective other items are determined. Respective second measures of usefulness of the respective other items are determined based on the respective first measures of usefulness and the respective measures of quality. The item and the other items are displayed ranked according to the respective second measures of usefulness.
Items from a collection of information are displayed ranked according to a relevance metric that is different from the second measures of usefulness.
The items displayed according to the relevance metric are from a different collection of information than the items displayed according to respective second measures of usefulness.
The first set of criteria is based on a search criterion received from a user.
The first set of criteria is based on a user profile.
The first set of criteria is based on a user""s prior search patterns.
Users are provided with at least one preferred interface for selecting the items from lists of items. The actual overall popularity of the item is determined without regard to selection of the item using interfaces other than a preferred interface.
Users are provided with opportunities to select items from lists of items ranked according to ranking criteria. Data about selection rates of items having particular ranks is collected. The selection rate of the item is predicted based on the rank of the item and the data about selection rates of items having particular ranks.
The respective predicted selection rates are multiplied by the respective measures of popularity of respective sets of criteria. The resulting products are added to determine the predicted overall popularity of the item.
Applying the anti-spoof criterion includes comparing the actual overall popularity of the item to a threshold value.
Applying the anti-spoof criterion includes comparing the actual overall popularity of the item in a particular time period to the actual overall popularity of the item in other time periods.
Applying the anti-spoof criterion includes determining the entropy of a selection rate of the item in a series of time periods and comparing the entropy to a threshold value.
The selection rate of an item is based on the number of times the item is selected during a given period relative to the number of queries made by users during that period.
The selection rate of an item is based on the number of times the item is selected during a given period relative to the number of selections of items during that period.
In general, in another aspect, a system for determining a measure of the usefulness of an item in a collection of information with respect to a first set of one or more criteria is provided. The system may include means for determining a first measure of the usefulness of the item with respect to the first set of criteria, means for determining a measure of the quality of the item, and means for determining a second measure of usefulness based on the first measure of usefulness and the measure of quality.
The system may include a computer processor, and a memory for holding the collection of information, wherein the computer processor is programmed to determine a first measure of the usefulness of the item with respect to the first set of criteria, determine a measure of the quality of the item, and determine a second measure of usefulness based on the first measure of usefulness and the measure of quality.
In general, in another aspect, a computer program residing on a computer readable medium is provided for determining a measure of the usefulness of an item in a collection of information with respect to a first set of one or more criteria. The computer program may include instructions for causing a computer to determine a first measure of the usefulness of the item with respect to the first set of criteria, determine a measure of the quality of the item, and determine a second measure of usefulness based on the first measure of usefulness and the measure of quality.
The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.